package com.leetcode.alibaba;

import java.util.Stack;

/**
 * 给定一个单链表的头结点pHead，长度为n，反转该链表后，返回新链表的表头。
 * 数据范围： n ≤ 1000
 * 要求：空间复杂度 O(1) ，时间复杂度 O(n)
 * 如当输入链表{1,2,3}时，
 * 经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
 */
public class 反转链表 {
	/**
	 * 利用栈
	 *
	 * @param head
	 * @return
	 */
	public ListNode reverseList(ListNode head) {
		Stack<ListNode> stack = new Stack<>();
		while (head != null) {
			stack.push(head);
			head = head.next;
		}
		if (stack.isEmpty()) {
			return null;
		}
		ListNode node = stack.pop();
		ListNode newHeader = node;

		while (!stack.isEmpty()) {
			node.next = stack.pop();
			node = node.next;
		}
		node.next = null;
		return newHeader;
	}

	/**
	 * 利用双链表
	 *
	 * @param head
	 * @return
	 */
	public ListNode reverseList2(ListNode head) {
		ListNode newHead = null;
		while (head != null) {
			//先保存访问的节点的下一个节点，保存起来
			//留着下一步访问的
			ListNode temp = head.next;
			//每次访问的原链表节点都会成为新链表的头结点，
			//其实就是把新链表挂到访问的原链表节点的
			//后面就行了
			head.next = newHead;
			//更新新链表
			newHead = head;
			//重新赋值，继续访问
			head = temp;
		}
		//返回新链表
		return newHead;
	}

	/**
	 * 利用双链表
	 *
	 * @param head
	 * @return
	 */
	public ListNode ReverseList(ListNode head) {
		if (head == null) {
			return head;
		}
		ListNode temp = head;
		ListNode next;
		ListNode newHead = new ListNode(0);
		while (temp != null) {
			next = temp.next;
			temp.next = newHead.next;
			newHead.next = temp;
			temp = next;
		}
		head = newHead.next;
		return head;
	}

	class ListNode {
		int val;
		ListNode next;

		ListNode(int val) {
			this.val = val;
		}
	}
}
